#include <iostream>
#include <string>
#include <vector>
#include "Log.hpp"
using namespace std;


#ifndef _AVL_TREE_
#define _AVL_TREE_
#include <iostream>
#include <chrono>

// AVL 树节点的定义
struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};

// 计算节点的高度
int getHeight(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

// 计算节点的平衡因子
int getBalanceFactor(Node* node) {
    if (node == nullptr) {
        return 0;
    }
    return getHeight(node->left) - getHeight(node->right);
}

// 更新节点的高度
void updateHeight(Node* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// 右旋操作
Node* rightRotate(Node* node) {
    Node* leftChild = node->left;
    node->left = leftChild->right;
    leftChild->right = node;
    updateHeight(node);
    updateHeight(leftChild);
    return leftChild;
}

// 左旋操作
Node* leftRotate(Node* node) {
    Node* rightChild = node->right;
    node->right = rightChild->left;
    rightChild->left = node;
    updateHeight(node);
    updateHeight(rightChild);
    return rightChild;
}

// 插入节点
Node* insertNode(Node* node, int key) {
    if (node == nullptr) {
        Node* newNode = new Node;
        newNode->key = key;
        newNode->left = nullptr;
        newNode->right = nullptr;
        newNode->height = 1;
        return newNode;
    }
    if (key < node->key) {
        node->left = insertNode(node->left, key);
    } else if (key > node->key) {
        node->right = insertNode(node->right, key);
    } else {
        // 如果 AVL 树中已经存在相同的键值，则不进行插入操作
        return node;
    }
    updateHeight(node);
    int balanceFactor = getBalanceFactor(node);
    if (balanceFactor > 1 && key < node->left->key) {
        // 左左情况，进行右旋操作
        return rightRotate(node);
    }
    if (balanceFactor < -1 && key > node->right->key) {
        // 右右情况，进行左旋操作
        return leftRotate(node);
    }
    if (balanceFactor > 1 && key > node->left->key) {
        // 左右情况，先对左子节点进行左旋操作，再对当前节点进行右旋操作
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if (balanceFactor < -1 && key < node->right->key) {
        // 右左情况，先对右子节点进行右旋操作，再对当前节点进行左旋操作
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

// 查找节点
Node* searchNode(Node* node, int key) {
    if (node == nullptr || node->key == key) {
        return node;
    }
    if (key < node->key) {
        return searchNode(node->left, key);
    }
    return searchNode(node->right, key);
}

// 中序遍历 AVL 树
void inorderTraversal(Node* node) {
    if (node == nullptr) {
        return;
    }
    inorderTraversal(node->left);
    std::cout << node->key << " ";
    inorderTraversal(node->right);
}

// 计算函数执行时间
template <typename Func, typename... Args>
auto measureTime(Func&& func, Args&&... args) {
    auto start = std::chrono::steady_clock::now();
    std::forward<Func>(func)(std::forward<Args>(args)...);
    auto end = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
}


#endif